package com.think.java.source.concurrency;

/**
 * @author willjo
 * 测试堆排序
 */
public class HeapSortTest {

    static void heap_sort(int array[], int length) {
        if (null == array || 0 == length) {
            return;
        }

        /* to make sure data starts at number 1 */
        _heap_sort(array , length);
    }

    /**
     * 构建大堆和调整大堆
     *
     * @param array
     * @param length
     */
    static void _heap_sort(int array[], int length) {
        int index = 0;
        int median = 0;
        construct_big_heap(array, length);

        for (index = length; index > 1; index--) {
            median = array[1];
            array[1] = array[index];
            array[index] = median;

            reconstruct_heap(array, 1, index - 1);
        }
    }

    /**
     * 构建大堆的细节操作部分
     *
     * @param array
     * @param length
     */
    static void set_sorted_value(int array[], int length) {
        int index = length;
        int median = 0;
        if (length == 1) {
            return;
        }

        while (index > 1) {
            if (array[index >> 1] >= array[index]) {
                break;
            }

            median = array[index];
            array[index] = array[index >> 1];
            array[index >> 1] = median;
            index >>= 1;
        }
    }

    static void construct_big_heap(int array[], int length) {
        int index = 0;

        for (index = 1; index <= length; index++) {
            set_sorted_value(array, index);
        }
    }

    /**
     * 大堆迭代调整
     *
     * @param array
     * @param index
     * @param length
     */
    static void reconstruct_heap(int array[], int index, int length) {
        int swap = 0;
        if (length < index << 1) {
            return;
        }

        if (length == index << 1) {
            adjust_leaf_position(array, index);
            return;
        }

        if (-1 != (swap = adjust_normal_position(array, index))) {
            reconstruct_heap(array, swap, length);
        }
    }

    /**
     * 对单分支节点和满分支节点分别处理
     *
     * @param array
     * @param index
     * @return
     */
    static int adjust_normal_position(int array[], int index) {
        int left = index << 1;
        int right = left + 1;
        int median = 0;
        int swap = 0;

        if (array[index] >= array[left]) {
            if (array[index] >= array[right]) {
                return -1;
            } else {
                swap = right;
            }
        } else {
            if (array[index] >= array[right]) {
                swap = left;
            } else {
                swap = array[left] > array[right] ? left : right;
            }
        }

        if (swap == left) {
            median = array[index];
            array[index] = array[left];
            array[left] = median;
        } else {
            median = array[index];
            array[index] = array[right];
            array[right] = median;
        }

        return swap;
    }

    public static Boolean adjust_leaf_position(int array[], int index) {
        int median = 0;
        if (array[index] > array[index << 1]) {
            return true;
        }

        median = array[index];
        array[index] = array[index << 1];
        array[index << 1] = median;
        return false;
    }

    static void test1()
    {
        int array[] = {1};
        heap_sort(array, array.length);
    }

    static void test2()
    {
        int array[] = {2, 1};
        heap_sort(array, array.length);
        assert(1 == array[0]);
        assert(2 == array[1]);
    }

    static void test3()
    {
        int array[] = {3, 2, 1};
        heap_sort(array, array.length);
        assert(1 == array[0]);
        assert(2 == array[1]);
        assert(3 == array[2]);
    }

    static void test4()
    {
        int array[] = {2, 3, 1};
        heap_sort(array, array.length);
        assert(1 == array[0]);
        assert(2 == array[1]);
        assert(3 == array[2]);
    }

    static void test5()
    {
        int array[] = {5,3, 4, 1};
        heap_sort(array, array.length);
        assert(1 == array[0]);
        assert(3 == array[1]);
        assert(4 == array[2]);
        assert(5 == array[3]);
    }

    static void test6()
    {
        int array[] = {2, 3,6, 8, 7};
        heap_sort(array, array.length);
        assert(2 == array[0]);
        assert(3 == array[1]);
        assert(6 == array[2]);
        assert(7 == array[3]);
        assert(8 == array[4]);
    }

    static void test7()
    {
        int array[] = {3,4,2,7,1,9,8,6,5};
        heap_sort(array, array.length);
        assert(1 == array[0]);
        assert(2 == array[1]);
        assert(3 == array[2]);
        assert(4 == array[3]);
        assert(5 == array[4]);
        assert(6 == array[5]);
        assert(7 == array[6]);
        assert(8 == array[7]);
        assert(9 == array[8]);
    }
    public static void main(String[] args) {
         test1();
         test7();
    }
}
